package Q449
import java.util.LinkedList

import java.util.Queue


/**
 * 序列化和反序列化二叉搜索树
 * @author 23737
 * @date 2022.5.11
 */
class Main {

}

fun main(args: Array<String>) {

}

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}


class Codec() {
    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if (root == null) return "#"
        val res = StringBuilder()
        val queue: Queue<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            val poll = queue.poll()
            res.append("#")
            if(poll!=null){
                res.append(poll.`val`)
                queue.add(poll.left)
                queue.add(poll.right)
            }

        }
        return res.toString()
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data == "#") {
            return null
        }
        val split = data.split("#".toRegex())
        val treeNode = TreeNode(Integer.parseInt(split[1]))
        val queue: Queue<TreeNode> = LinkedList<TreeNode>()
        queue.add(treeNode)
        for (i in 3 until split.size step 2) {
            val poll = queue.poll()
            if (split[i - 1].isNotEmpty()) {
                poll.left = TreeNode(Integer.parseInt(split[i - 1]))
                queue.add(poll.left)
            }
            if (split[i].isNotEmpty()) {
                poll.right = TreeNode(Integer.parseInt(split[i]))
                queue.add(poll.right)
            }
        }
        return treeNode
    }
}